// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-29 17:25
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

@SuppressWarnings("ALL")
public class MaxSumOfThreeSubarrays {
    /**
     * 三个无重叠子数组的最大和
     */
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        /*
            1 多状态动态规划实现 + 前缀和 + 逆序DP
         */
        int n = nums.length;
        /*-----构建前缀和数组-----*/
        /*
            通过前缀和大量减少去求区间数据和
         */
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        /*-----状态转移-----*/
        /*
            为了是状态转移数组和前缀和的数组的序号对上，状态数组的空间大小设置为4
            f[n+1][j]:记录了数组最后一个元素所能组成的j个三元组之和
         */
        int[][] f = new int[n + 10][4];
        for (int i = n - k + 1; i >= 1; i--) {
            for (int j = 1; j < 4; j++) {
                f[i][j] = Math.max(f[i + 1][j], f[i + k][j - 1] + sum[i + k - 1] - sum[i - 1]);
            }
        }
        /*-----通过状态数组获取无重叠三个子数组之和-----*/
        /*
            i+=k表示当前元素在最优解中，而且下一个子数组不能和当前数组重合
         */
        int i = 1, j = 3, idx = 0;
        int[] ans = new int[3];
        while (j > 0) {
            if (f[i + 1][j] > (f[i + k][j - 1] + sum[i + k - 1] - sum[i - 1])) {
                i++;
            } else {
                ans[idx++] = i - 1;
                i += k;
                j--;
            }
        }
        return ans;
    }
}
